Flow control mechanisms in computer networks govern the transfer of packets from a source node to a destination node (in the art, and in the following, the term source may be used interchangeably with sender, destination with receiver, and node with agent). Typical flow control mechanisms include negative-acknowledgment (NACK)/retry, drop/source-timeout/retry, credit/debit, and network buffering. Generally, a source or sending node or agent sends a packet to a destination or sink node or agent, where the destination node has a finite amount of “ingress buffering” for holding packets it has received from the source node prior to processing.
In a credit/debit flow mechanism for a network, a source node on the network keeps track of the number of buffers available at a destination node through the use of “credits” and “debits.” A source node will only send a packet or, in general, data, to a destination node if the source node knows there is a free buffer available at the destination node to accept the packet. When the source node sends a packet to the destination node, the source node “debits” (decrements) a local count of the number of free buffers the destination node has available. When the destination node removes a packet from its incoming buffers, the destination node sends a “credit” message back to the source node, and the source node “credits” (increments) the local count of the number of free buffers the destination node has available.
The destination node can choose to statically allocate its buffers amongst the sending nodes, whereby a fixed number of the destination node's incoming buffers are reserved for each of the M source nodes. If the destination node has a total of N incoming buffers, it may equally allocate N/M buffer entries to each source node. This works well if traffic to the destination node from all the source nodes is exactly uniform. But any deviation from uniform traffic will cause inefficiencies in the utilization of the N buffers. A degenerate form of this design is to provide enough buffering at the destination node such that all of the packets that the source nodes may send simultaneously can be accommodated. In other words, if each of the M source nodes can have P packets in-flight, then each destination node must have P*M buffer entries. The drawback with this mechanism is that it leads to an inefficient, area-hungry design because the buffer utilization is usually very low.
The destination node may instead allocate N credits, one for each of its receiving buffers. The source nodes need to share the N credits. The simplest way to share the credits amongst S distributed sending agents is to give each agent N/S credits for the receiving agents buffers. This promotes fairness amongst the agents, but does not handle imbalanced demand from the agents optimally. For example, when a single agent has many messages to send, and the others have none, the single agent is limited to using N/S credits, which will limit the message bandwidth from the agent.